#include<bits/stdc++.h>
using namespace std;

class Solution
{
private:
    /* data */
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid){
        if(grid[0][0]==1){
            return -1;
        }
        int dire[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        queue<pair<int,int>> q;
        int n=grid.size();
        q.emplace(0,0);
        grid[0][0]=1;
        int res=1;
        while(!q.empty()){
            int t=q.size();
            while(t--){
                auto [x,y]=q.front();
                q.pop();
                if(x==n-1 && y==n-1){
                    return res;
                }
                for(int i=0;i<8;++i){
                    int nx = x + dire[i][0];
                    int ny = y+dire[i][1];
                    if(nx<0 || nx>=n || ny<0 || ny>=n){
                        continue;
                    }
                    if(grid[nx][ny]==0){
                        q.emplace(nx,ny);
                        grid[nx][ny]=1;
                    }
                }
            }
            ++res;
        }
        return -1;
    }
};


int main(int argc, char const *argv[])
{
    vector<vector<int>> grid = {{0,1},{1,0}};
    Solution s;
    cout<<s.shortestPathBinaryMatrix(grid)<<endl;
    return 0;
}
